|
A Use-Definition Chain (''UD Chain'') is a data structure that consists of a use, U, of a variable, and all the definitions, D, of that variable that can reach that use without any other intervening definitions. A definition can have many forms, but is generally taken to mean the assignment of some value to a variable (which is different from the use of the term that refers to the language construct involving a data type and allocating storage). A counterpart of a ''UD Chain'' is a Definition-Use Chain (''DU Chain''), which consists of a definition, D, of a variable and all the uses, U, reachable from that definition without any other intervening definitions. Both UD and DU chains are created by using a form of static code analysis known as data flow analysis. Knowing the use-def and def-use chains for a program or subprogram is a prerequisite for many compiler optimizations, including constant propagation and common subexpression elimination. ==Purpose== Making the use-define or define-use chains is a step in liveness analysis, so that logical representations of all the variables can be identified and tracked through the code. Consider the following snippet of code: int x = 0; / * A */ x = x + y; / * B */ / * 1, some uses of x */ x = 35; / * C */ / * 2, some more uses of x */ Notice that x is assigned a value at three points (marked A, B, and C). However, at the point marked "1", the use-def chain for x should indicate that its current value must have come from line B (and its value at line B must have come from line A). Contrariwise, at the point marked "2", the use-def chain for x indicates that its current value must have come from line C. Since the value of the x in block 2 does not depend on any definitions in block 1 or earlier, x might as well be a different variable there; practically speaking, it ''is'' a different variable — call it x2.int x = 0; / * A */ x = x + y; / * B */ / * 1, some uses of x */ int x2 = 35; / * C */ / * 2, some uses of x2 */ The process of splitting x into two separate variables is called live range splitting. See also static single assignment form.抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Use-define chain」の詳細全文を読む スポンサード リンク
|